package com.pan.alg.niuke.tree;

import java.util.LinkedList;
import java.util.Queue;

import static com.pan.alg.niuke.tree.TreeUtil.generateTree;

/**
 * 描述
 * 给定一个二叉树，确定他是否是一个完全二叉树。
 *
 * 完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）
 *
 * 数据范围：节点数满足 1 \le n \le 100 \1≤n≤100
 */
public class TreeIsCompleteTree {

    public boolean isCompleteTree (TreeNode root) {
        // write code here
        Queue<TreeNode> levelNode = new LinkedList();
        levelNode.offer(root);
        boolean hasNull =false;
        while (!levelNode.isEmpty()){
            int size = levelNode.size();

            for (int i = 0; i < size; i++) {
                TreeNode current = levelNode.poll();
                if(current!=null&&hasNull){
                    return false;
                }
                if(current==null){
                    hasNull=true;
                    continue;
                }
                levelNode.offer(current.left);
                levelNode.offer(current.right);
            }
        }
        return true;
    }





    public static void main(String[] args) {
        int[] tree = new int[]{1,2,3,4,5,6};
        TreeNode head = generateTree(tree);
        TreeIsCompleteTree treeis = new TreeIsCompleteTree();
        boolean oo = treeis.isCompleteTree(head);
        System.out.println(oo);
    }




}
